[書評] 「アルゴリズム的思考力が身につく！ プログラミングコンテストAtCoder入門」は競プロ・アルゴリズム勉強したいけど何をしたら良いかわからない人におすすめの一冊

こんにちは、AWS事業本部コンサルティング部に所属している今泉(@bun76235104)です。

今回は「AtCoderや競技プログラミングを始めたい・一生使えるアルゴリズムの勉強をしてみたい」という方におすすめの書籍について「書評」を書かせていただきました。

• タイトル: アルゴリズム的思考力が身につく！ プログラミングコンテストAtCoder入門
• 出版社: KADOKAWA
• 著者(敬称略)： 大槻兼資
  • 監修: AtCoder株式会社
• 出版社の書籍情報リンク:　「アルゴリズム的思考力が身につく！ プログラミングコンテストAtCoder入門」 大槻　兼資[ＰＣ・理工科学書] - KADOKAWA

AtCoder・競技プログラミングはプログラミングを使ったスポーツ

本書では、「AtCoderの始め方・どこを目指すために、どのようなアルゴリズムを学習して、どのような練習問題を解いていくかという」ことを丁寧にナビゲートしてくれます。

AtCoderは「アルゴリズムに関する問題をプログラミングを使って解く」ことを競技化したコンテストを開催してくれるサービスです。

コンテストは「制限時間内にできるだけ多くの問題を解くスポーツ」のようなもので、このコンテストの出来次第で自身のレートが上昇・下降していくので、レベルアップ感を楽しむことができます。

コンテストはほぼ毎週開かれているので、すぐにでも始めることができて非常におすすめです！

他人と比べずに楽しむのが秘訣

書籍の紹介の前に知っておくべきと私が思う一番重要なマインドセットです。

AtCoder(競技プログラミング)では if for while などの制御構文は当たり前のように理解していて、様々な設計技法に習熟しているような方でも「数学的素養」「アルゴリズムへの知見」などで大きくパフォーマンスが変わります。

• 数学的素養
• アルゴリズム力・論理的思考力
• 思考をプログラムで具体化する力

これらの総合力でパフォーマンスが決まるものと思った方が良いでしょう。

私のように「数学が苦手だけど実務ではコードを書いていた」ような人が、「最近プログラムを始めた理系」の方や、「数学パズルが得意だけど、プログラム歴ほぼなし」のような方にパフォーマンスで劣る可能性が十分にあります。

現に私は1年半ほど前に当時の同僚に導かれAtCoderを始めたのですが「エンジニア歴はそんなに変わらないのに高いパフォーマンスを出しまくる方」と「問題を全然解けない自分」を比べてしまい、挫折したことがあります。

そんな私でも人と比べることをやめて、自分の今のレベルに合った問題・ちょっとレベルが高い問題を解くことの重要性に気づいた後は、楽しく競技プログラミングの勉強を行えるようになりました。 (レベルはまだまだ低いです)

これから競プロを始める方は「さらっと書いてある解説の意味がわからない」「全然解けなくて面白くない」と感じるかもしれませんが、「まぁ今は解けないだけか」とさらっと思うくらいのマインドセットをお勧めします！

本の構成(目次)

全6章の構成になっていて、1~2章でAtCoderの説明・始め方・本書が目指すレベルの紹介等、3~6章でレベルに応じた問題の紹介と解説がされています。

• 第１章　AtCoderとは
• 第２章　AtCoderの始め方
• 第３章　初級編～ここからスタート！～
• 第４章　中級編～典型を徹底マスター～
• 第５章　計算量
• 第６章　上級編～本格的なアルゴリズムの世界へ～

感想

競プロを始めたいけど何をしたら良いかわからない人にピッタリの入門書である

「一生使えるアルゴリズムを身につけないなぁ・・・」とか「競プロってやつをやってみたいなぁ・・・」と考えている方に本書はぴったりだと思います。

本書では1章・2章で日本語で競プロを始めることのできるAtCoderの紹介と本書が目指すレベルを解説し、3章からはレベルに応じたサンプル問題と練習問題を数多く提示してくれています。

またコラム（ワンポイント）に非常に有用なことを書いてくださっています。「解説が理解できないとき」「練習のために解く問題の難易度設定」などは特に重要だと感じました。

私はこれらの考え方・調べ方を知らなかったことが挫折の一因になっていました。

まさに「魚の釣り方」を教えてくれる一冊と言えると思います。

特にこの界隈は「入門」と書いてある書籍だが、入門者にはハードルが高い。ということが割とあると考えているのですが、本書は本当に入門者を意識して作られているなと感じました。

レベル感・自分がどこを目指せば良いか分かる

AtCoderにはレーティングシステムがあり、本書内では以下の茶色をまず目指すことが最初に明言されています。

レートの色	実力のイメージ	備考
赤色	世界トップレベルの実力です	上位0.4%
橙色	日本トップレベルの実力です	上位1%
黄色	アルゴリズムに特化した研究開発の場面で重宝される実力です	上位3%
青色	東証プライム上場企業で1人いるかどうかの実力です	上位7%
水色	大多数のIT企業でこれ以上のアルゴリズム力を必要としない程度の実力です	上位15%
緑色	アルゴリズム専門書に相当する内容を一通り理解し、自在に使いこなせる実力です	上位30%
茶色	アルゴリズムの専門書に相当する内容を一通り理解することで到達できる実力です	上位50%
灰色	コンテストに1回以上参加すれば灰色以上になりれます

AtCoderの社長で代表取締役で自身も赤色コーダーである高橋直大氏のブログによると、以下のように茶色のレベルに対する説明をしてくださっています。

茶色で保証できる実力ですが、正直、AtCoder内ではあまり高いレベルではありません。ただ、ここにたどり着く前に辞めてしまう人が多いので、十分にやる気がある人であるとは言えるでしょう。 なお、他社転職サイトと比較すると、このレーティングでも上位1~2%の最高ランクに到達出来る人が数割いるため、一般的には十分高いレベルであると言えます。

スキル的に確実に保証出来る点は、 標準入出力、if、forなどの単純な操作はできる 問題文を正しく理解し、計算量を考えない仕様通りの実装をすることが出来る の２点です。ただし、完全に上の能力しか持っていないと茶色になることはできず、

MARCH理系学部以上に入れる程度の数学力や論理的思考力があり、数学的な工夫が必要な問題を正解出来る 典型アルゴリズムに関する知識を多く持ち、探索による全列挙や単純な動的計画法など、典型的な問題に正解することが出来る。 コーディングや読解速度が早く、単純な問題を早く正確に実装することが出来る などの特徴を持っていなければ、茶色になることはできません。

※ 少し古い記事ですので、今現在の難易度との関係は不明です。個人的に現在はもう少し難易度が上がっているような気がしています。

一見茶色とすると上位50%と大したことがないように感じますが、十分に歯応えのある目標だということがわかります。

なお、2022年8月12日現在、私自身も灰色レートではあるものの、おそらく数ヶ月以内には茶色に到達するかな？というレベルなので、決して達人が競プロを普及している訳ではありません。

この界隈では色が変わった時に「色変記事」なるものを書くことが風習なようなので、私も書けるように精進したいと思います。

「アルゴリズム？計算量？それ何の役に立つの？」への特効薬

「二分探索法」

実際に自分でアルゴリズムを組んだことがなくても、エンジニアなら聞いたことがある方も多いのではないでしょうか。

私はこれを聞いた時に「基本情報技術者や応用情報技術者試験で出るアレね。最初から最後まで順に探すより効率いいんだよね。」という感想でした。

実際問題として、例えば配列のソートを考えても各言語がいい感じにソート用の関数を用意してくれているので、いつアルゴリズムの考えを使えば良いのかわかりませんでした。

しかし、安心してください。競プロをやっていくと、いろいろなアルゴリズムを実践を通して身につけることができます。

AtCoderにおいても「2秒以内に答えを出力して下さい」というような 時間計算量 といわれる制約があります。

「愚直に1から調べ上げていたら間に合わない問題を、どのように少ない計算量で答えを導くか」という思考力を自然と身につけることができます。

しかもこの書籍の場合、「○○というテクニックはこう使用します」という解説に止まらず、実際のAtCoderの問題を練習問題としてまとめてくれていますので、手を動かしながら効率的に学ぶことができます。

計算量の例: 数字が素数かどうか判定する

計算量を意識する必要がある問題を1つ上げてみますが、興味のない方はスルーしてください

こちらの問題を見てみると X 以上の素数のうち、最小のものを求めよ。(2≤X≤10の5乗) という非常にシンプルな問題です。

素数の定義も 2 以上の整数であって、1 と自分自身を除くどの正の整数でも割り切れないようなもののことです という風に書いてくれています。

業務でコードを書いているようなプログラマであれば、以下のような素数判定用のコードをそう時間をかけずに書くことができるのではないでしょうか？

def is_prime(n: int) -> bool:
    # 2からnまで n ÷ 2, n ÷ 3 ... n ÷ nと割り切れるかどうか調べていく
    for i in range(2, n+1):
        if n % i == 0:
            # nになるまでに割り切れる数があれば素数ではない
            return False
    return True

例えばnが19の場合

• 19÷2
• 19÷3
• 19÷4
• ...
• 19÷19

と繰り返していき、「19になるまでに割り切れてしまう数があれば素数ではない」となるわけですね。

計算も間違ってなさそうだし、行ける気がしますが・・・このコードではいくつかのサンプルで時間切れ(TLE)になってしまい、全問正解(AC)を出すことはできません。

こちらの記事に以下のように、AtCoderのジャッジにおける計算量について記述があります。

制限時間は2秒です。AtCoderのジャッジでは1秒あたり10の8乗回程度の計算が可能です。

とあるように、この計算だと 99972 のような大きめの数字の場合

• 2~99972までを is_prime 関数で判定(約10万回(10の5乗)の計算)
• 判定した結果素数ではなかったので 次は 99973 を調べる
• 2~99973までを is_prime 関数で判定(約10万回(10の5乗)の計算)
• 判定した結果素数ではなかったので、次は99974 を調べる
• ....

と計算していくことになり 非常に大きな計算量になってしまうためです。

これについて、より計算量の少ないコードを考えていくわけです。

なお、今回の場合は以下のような考えで計算量を減らすことができます。(こちらの記事も書籍筆者が書いているものです)

例えば X=16 として考えて紙に書き出して見るとわかりやすいです。

X = A * Bという風に考えてみると以下のように約数を列挙できます(A,Bは正の整数)

• 1 × 16
• 2 x 8
• 4 x 4
• 8 x 2
• 16 x 1

とみてみると、4 x 4を境に後はAとBが逆になっているだけということに気づきます。

36でも試してみます。

• 1 x 36
• 2 x 18
• 3 x 12
• 4 x 9
• 6 x 6
• 9 x 4
• 12 x 3
• 18 x 2
• 36 x 1

こちらも 6 x 6 を境にAとBが逆になっているだけです。

このように書き出してみることで「Nが素数かどうか判定する時には、2からNまで割り切れるか試すのではなく、2からNの平方根まで試せば良いのかな？」 という気づきを得ることができます。

当時の私は全く意味がわからなかったのですが、このような問題を繰り返すことで多少なりとも数学的な考え方・計算量を気にするコーディングができるようになってきた気がします。

全部の問題を解く必要はない。難易度(Difficulty)を見てつまみ食いが良い

一点注意した方が良いと思ったのが、「節末にある練習問題全てを順番に解こうとする」と挫折する可能性が高くなります。

関連する問題を練習問題としてまとめてくださっているため、多様な難易度の問題が列挙されています。

本書のコラムにも「練習のために解く問題の難易度設定」というワンポイントアドバイスがありますが、本書の問題には極力「Difficulty」という難易度の目安を記載してくださっています。

このDifficultyを見て、自分のレベルに高そうな問題は無視して、解けそうな問題だけサクサク解いて、さっさと本を読み切ってしまいましょう。

2周目以降や、ある程度レベルが上がってきたと感じるタイミングでDifficultyがちょっと高めの問題にチャレンジすることがおすすめです。

かつて挫折した私が個人的におすすめする1周目で解いてしまうDiffucultyです。簡単と思った場合は、より高いレベルにチャレンジして、レベルが高いと思ったらDifficultyがもう少し低い問題に設定してみてください。

数学が得意	プログラミングの実務経験あり	おすすめDifficulty
いいえ	なし	100~150程度まで
いいえ	あり	200~250程度まで

数学が得意な方は正直、150以下の問題でプログラム自体に慣れてしまえば、問題によってはDiffuculty300 ~ 400の問題も楽に解けてしまうかもしれません。 (プログラミングというより、計算一発で求めるような問題も割とあるため)

最後に

私はAtCoderで一度挫折していますが、再び楽しくなって1年半ぶりくらいにやり始めています。

正直、自分が入門の時に本書があれば・・・と思うほど、入門者のことを考えてくださった書籍だと感じています。

本書はまず自分に合った問題を解きつつ、1周する。問題の難易度を少し上げて2周・・・とすることがより効率的だと感じました！

AtCoder(競プロ)は存外やり始めるハードルは低いと思いますので、是非本書をきっかけに競プロの世界を味わってみてください！